The possibilities for parallel computing have greatly increased with the availability of multiprocessor systems. A multiprocessor system increases processing by executing tasks or processes on two or more processors. Depending on the multiprocessor system design, these tasks may run on several or several hundred processors concurrently. Managing concurrent execution on multiprocessor systems involves safeguarding data from modification by multiple processes. Indeterminate results, deadlocks, and data corruption may result if multiple tasks modify or access the same dataset. Accordingly, concurrent execution conditions on multiprocessor systems are managed to assure the proper access of data.
Conventional solutions resolve concurrent execution conditions using different types of locks or dividing processes into multiple domains. For example, fine-grained locking manages concurrent execution on multiple processors by dividing a task into many smaller pieces of code. Placing locks around these small pieces of code keeps them from being accessed or modified by other tasks. However, fine-grained locking is expensive in terms of computer processing, and requires code to be rewritten for each task. On the other hand, data partitioning operates differently from the fine-grained locking approach. Instead of using locks, data partitioning divides tasks (e.g., threads) along functional barriers into domains of tasks having similar functionality. The functional barriers represent a logical separation of tasks into different domains where these tasks can be run in parallel on different processors without conflict, with minimal sharing of data, and with minimal use of locks.
In data partitioning, threads to be executed are divided into a set of domains according to their functionality and tasks they perform. Therefore, a “domain,” as used herein, refers to a grouping of threads based on a common functionality. Based upon this division, threads in the different domains may be scheduled to execute in parallel on multiple processors because, for example, threads in different domains generally have different functionalities and do not operate on the same data for the most part, thereby allowing them to execute in parallel without conflict. However, threads within each domain that share data and data structures can be limited to serialized execution on a single processor to avoid data contention or corruption.
Referring to FIG. 1, a high-level block diagram showing an example of data partition hierarchy. This hierarchy permits certain subdomains to execute their processes in parallel with processes of other subdomains, but prevents other subdomains from executing their processes in parallel with processes of any other subdomain or with processes of some other subdomains. Any subdomains that have an ancestral (vertical) relationship to each other within the hierarchy are precluded from executing their processes in parallel with each other, whereas subdomains that do not have an ancestral relationship to each other within the hierarchy are normally permitted to execute their processes in parallel with each other.
The hierarchy of subdomains can be thought of as a hierarchy of reader and writer locks. When running a process in a subdomain, that subdomain in essence has an exclusive writer lock on all of its child subdomains, and a shared reader lock on all of its ancestors subdomains. Note that for purposes of this description, the subdomain hierarchy can be thought of as an inverted tree structure, where descendency goes from bottom to top in FIG. 1. Thus, in FIG. 1 the “child” of a given subdomain (if it has any) would be located above that subdomain and the parent of that subdomain (if it has any) would be located below it. The hierarchy of subdomains in FIG. 1 first includes a Serial subdomain. Above the Serial subdomain, the hierarchy further includes an Aggregate subdomain. Above the Aggregate subdomain, the hierarchy further includes an Aggr-VBN subdomain and one or more volume (“Vol”) subdomains, i.e., one Vol subdomain for each volume. Above the Vol subdomains, the hierarchy further includes one or more Volume-Logical (“Vol-Logical”) subdomains, one for each volume, and one or more Volume-VBN (“Vol-VBN”) subdomains, one for each volume. Above each Vol-Logical subdomain, the hierarchy further includes one or more Stripe subdomains. As used in this description, the term “VBN” stands for volume block number and means a block index into a flat data container, such as either an aggregate (e.g., in the case of Aggr-VBN) or a volume (e.g., in the case of Vol-VBN).
Vol I inherits the permissions of the subdomains located above it. Therefore, a thread from this subdomain could run and perform any of the operations that are typically associated with the subdomains that exist above it. However, threads from two different partitions are unable to run at the same time if they share a common path to the ancestor (e.g., stripe N and Vol-Logical_1). In this case, stripe N cannot run simultaneous with Vol-Logical_1 because these subdomains share permissions that are inherited downward. Vol-Logical_1 will have inherited the permissions of StripeN. Allowing two threads with the same permissions to run can cause a race because the subdomains are protected exclusively by the data partitioning. Therefore, data partition ensures that only one thread running at a time has acquired the permission necessary.
The present disclosure is susceptible to various modifications and alternative forms, and some representative embodiments have been shown by way of example in the drawings and will be described in detail herein. It should be understood, however, that the inventive aspects are not limited to the particular forms illustrated in the drawings. Rather, the disclosure is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the disclosure as defined by the appended claims.